import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution90 {

    public static void main(String args[]) {
        Solution90 s = new Solution90();
        System.out.println(s.subsetsWithDup(new int[]{1, 2, 2}));
    }

    HashMap<List<Integer>, Integer> mp;
    List<List<Integer>> ret;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        mp = new HashMap<>();
        ret = new ArrayList<>();
        dfs(nums, 0, new ArrayList<>());
        return ret;
    }

    public void dfs(int[] nums, int st, List<Integer> l) {
        if (st == nums.length) {
            if (!mp.containsKey(l)) {
                ret.add(l);
                mp.put(l, 1);
            }
            return;
        }
        dfs(nums, st + 1, new ArrayList<>(l));
        l.add(nums[st]);
        dfs(nums, st + 1, new ArrayList<>(l));
    }
}
